package dynamicprogramming;

import jdk.nashorn.internal.ir.IfNode;

/**
 * @author kaho
 * @since 2021/3/8
 */
public class _132_分割回文串II {

    /**
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
     *
     * 返回符合要求的 最少分割次数 。
     * @param s
     * @return
     */
    public int minCut(String s) {
        if(s.length() < 2){
            return 0;
        }

        int[] dp = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            dp[i] = i;
        }

        for (int i = 1; i < s.length(); i++) {
            if(isTure(s, 0, i)){
                dp[i] = 0;
                continue;
            }

            for (int j = 0; j < i; j++) {
                if (isTure(s, j+1, i)) {
                    dp[i] = Math.min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[s.length()-1];
    }

    private boolean isTure(String s, int left, int right) {
        while (left<right){
            if (s.charAt(left)!=s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
